#include <stdlib.h>
#include <string.h>

#define DICT_OK 0
#define DICT_ERR 1

typedef struct dictEntry {
	void *key;
	void *value;
	struct dictEntry *next;
} dictEntry;

typedef struct dict {
	dictEntry **table;
	unsigned int size;
	/**
	 * sizemask = size-1
	 * 如果size是2的n次幂或0,hash%size = hash&sizemask
	 */
	unsigned int sizemask;
	unsigned int used;
} dict;

static unsigned int dictGenHashFunction(const unsigned char *buf, int len) {
    unsigned int hash = 5381;

    while (len--)
        hash = ((hash << 5) + hash) + (*buf++); 
    return hash;
}

static unsigned int dictStringHashFunction(const void *key) {
	return dictGenHashFunction(key, strlen(key));
}

static int _dictExpand(dict *ht, unsigned int size) {
	if (ht->used > size) 
		return DICT_ERR;
	dict *n = malloc(sizeof(*n));
	n->size = size;
	n->sizemask = size - 1;
	n->table = malloc(size * sizeof(dictEntry*));
	n->used = ht->used;
	memset(n->table, 0, size*sizeof(dictEntry*));

	int i;
	for (i = 0; i < ht->size && ht->used > 0; i++) {
		dictEntry *he, *nextHe;
		if (ht->table[i] == NULL)
			continue;
		he = ht->table[i];
		while (he) {
			unsigned int h;
			nextHe = he->next;
			h = dictStringHashFunction(he->key) & n->sizemask;
			he->next = n->table[h];
			n->table[i] = he;
			ht->used--;
			he = nextHe;
		}
	}
	free(ht->table);
	*ht = *n;
	return DICT_OK;
}

static int _dictExpandIfNeeded(dict *ht) {
	if (ht->size == 0) 
		return _dictExpand(ht, 16);
	else if (ht->used == ht->size)
		return _dictExpand(ht, ht->size*2);
	return DICT_OK;
}

static int _dictKeyIndex(dict *ht, const void *key) {
	unsigned int h;
	dictEntry *he;
	if (_dictExpandIfNeeded(ht) == DICT_ERR)
		return -1;
	h = dictStringHashFunction(key) & ht->sizemask;
	he = ht->table[h];
	while (he) {
		if (strcmp(key, he->key) == 0)
			return -1;
		he = he->next;
	}
	return h;
}

dict *dictCreate() {
	dict *ht = malloc(sizeof(*ht));
	ht->table = NULL;
	ht->size = 0;
	ht->sizemask = 0;
	ht->used = 0;
	return ht;
}

int dictAdd(dict *ht, void *key, void *value) {
	unsigned int index;
	dictEntry *entry;

	if ((index = _dictKeyIndex(ht, key)) == -1) 
		return DICT_ERR;
	entry = malloc(sizeof(*entry));
	entry->key = key;
	entry->value = value;
	entry->next = ht->table[index];
	ht->table[index] = entry;
	ht->used++;
	return DICT_OK;
}

dictEntry *dictFind(dict *ht, const void *key) {
	unsigned int h;
	dictEntry *he;

	if (ht->size == 0)
		return NULL;
	h = dictStringHashFunction(key) & ht->sizemask;
	he = ht->table[h];
	while (he) {
		if (strcmp(key, he->key) == 0) 
			return he;
		he = he->next;
	}
	return NULL;
}

void main() {
	dict *d = dictCreate();
	dictAdd(d, "aaa", "aaa");
	dictAdd(d, "bbb", "bbb");
	dictAdd(d, "ccc", "ccc");

	dictEntry *entry = dictFind(d, "bbb");
	printf("node = %s\n", entry->value);
}
